# 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
# 如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
#
# 注意你不能在买入股票前卖出股票。
#
# 输入: [7,1,5,3,6,4]
# 输出: 5
# 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
#
# 输入: [7,6,4,3,1]
# 输出: 0
# 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

# https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock


# 小黄鸭整理思路
# 1.最特殊的 [] 直接判断返回0
# 2.不能在买入股票前卖出股票 所以先到找下降拐点 大小大 的这个位置key_min
# 3.没有下降拐点的情况 : 整体递减 返回0
# 4.找到上升拐点 小大小 这个位置 条件:key_min存在(not 预设)
# 5.没有上升拐点 : 整体递增 返回 最末尾-第一个 的值
# 6 复数个拐点 比如   [5,1,2,7,2,6,4,3,5,3,0,9]
#   直到出现下降拐点前 continue
#   拿到第一个拐点1之后 ,遍历至上升拐点7 记录diff
#   后面如果遇到新的下降拐点 比现有记录的更小 则记录新的 并重置上升拐点的记录 否则保持
#   如果遇到新的上升拐点 比现有记录更大 则记录新的  减去原有的下降拐点更新diff
# 7.最右临界值,无法作为拐点处理 单独判断减去最小拐点的差 与现有diff对比
class Solution_new:
    def maxProfit_new(self, prices):
        # 1
        if len(prices) == 0:
            return 0
        i = 0
        max_i = len(prices)
        check_down = False
        check_up = False
        # keep_max = 0
        # keep_min = 0
        keep_diff = 0
        for price in prices:
            if price > 9251:
                print("wo shi da shu ",price)
            if i == 0:
                # first
                keep_min = price
                keep_max = price
                i += 1
                continue
            if i < max_i-1:
                # 除去最后一个的中间部分
                if prices[i-1] >= price and prices[i+1] > price:
                    if check_down:
                        if price < keep_min:
                            keep_min = price
                            check_up = False
                        else:
                            pass
                    else:
                        if price < keep_min:
                            keep_min = price
                            check_down = True
                elif prices[i-1] < price and prices[i+1] <= price:
                    if not check_down:
                        keep_max = price
                        keep_diff = price - keep_min if (price - keep_min) > keep_diff else keep_diff
                        check_up = True
                    else:
                        if check_up:
                            if price > keep_max:
                                keep_max = price
                                keep_diff = price - keep_min
                            else:
                                keep_diff = price - keep_min if (price - keep_min) > keep_diff else keep_diff
                                keep_max = price
                                check_up = True
                                pass
                        else:
                            keep_max = price
                            check_up = True
                            keep_diff = price - keep_min
                else:
                    pass

            if i == max_i - 1:
                print(check_down, check_up, keep_max, keep_min, keep_diff)
                # final
                if check_up and price > keep_max:
                    keep_diff = price - keep_min
                elif price > prices[i-1]:
                    keep_diff = price - keep_min if price - keep_min > keep_diff else keep_diff

            i += 1
        print(check_down, check_up, keep_max, keep_min, keep_diff)
        return keep_diff


# anwser = Solution_new()
# result = anwser.maxProfit_new([397,6621,4997,7506,8918,1662,9187,3278,3890,514,18,9305,93,5508,3031,2692,6019,1134,1691,4949,5071,799,8953,7882,4273,302,6753,4657,8368,3942,1982,5117,563,3332,2623,9482,4994,8163,9112,5236,5029,5483,4542,1474,991,3925,4166,3362,5059,5857,4663,6482,3008,3616,4365,3634,270,1118,8291,4990,1413,273,107,1976,9957,9083,7810,4952,7246,3275,6540,2275,8758,7434,3750,6101,1359,4268,5815,2771,126,478,9253,9486,446,3618,3120,7068,1089,1411,2058,2502,8037,2165,830,7994,1248,4993,9298,4846,8268,2191,3474,3378,9625,7224,9479,985,1492,1646,3756,7970,8476,3009,7457,8922,2980,577,2342,4069,8341,4400,2923,2730,2917,105,724,518,5098,6375,5364,3366,8566,8838,3096,8191,2414,2575,5528,259,573,5636,4581,9049,4998,2038,4323,7978,8968,6665,8399,7309,7417,1322,6391,335,1427,7115,853,2878,9842,2569,2596,4760,7760,5693,9304,6526,8268,4832,6785,5194,6821,1367,4243,1819,9757,4919,6149,8725,7936,4548,2386,5354,2222,8777,2041,1,2245,9246,2879,8439,1815,5476,3200,5927,7521,2504,2454,5789,3688,9239,7335,6861,6958,7931,8680,3068,2850,1181,1793,7138,2081,532,2492,4303,5661,885,657,4258,131,9888,9050,1947,1716,2250,4226,9237,1106,6680,1379,1146,2272,8714,8008,9230,6645,3040,2298,5847,4222,444,2986,2655,7328,1830,6959,9341,2716,3968,9952,2847,3856,9002,1146,5573,1252,5373,1162,8710,2053,2541,9856,677,1256,4216,9908,4253,3609,8558,6453,4183,5354,9439,6838,2682,7621,149,8376,337,4117,8328,9537,4326,7330,683,9899,4934,2408,7413,9996,814,9955,9852,1491,7563,421,7751,1816,4030,2662,8269,8213,8016,4060,5051,7051,1682,5201,5427,8371,5670,3755,7908,9996,7437,4944,9895,2371,7352,3661,2367,4518,3616,8571,6010,1179,5344,113,9347,9374,2775,3969,3939,792,4381,8991,7843,2415,544,3270,787,6214,3377,8695,6211,814,9991,2458,9537,7344,6119,1904,8214,6087,6827,4224,7266,2172,690,2966,7898,3465,3287,1838,609,7668,829,8452,84,7725,8074,871,3939,7803,5918,6502,4969,5910,5313,4506,9606,1432,2762,7820,3872,9590,8397,1138,8114,9087,456,6012,8904,3743,7850,9514,7764,5031,4318,7848,9108,8745,5071,9400,2900,7341,5902,7870,3251,7567,2376,9209,9000,1491,7030,2872,7433,1779,362,5547,7218,7171,7911,2474,914,2114,8340,8678,3497,2659,2878,2606,7756,7949,2006,656,5291,4260,8526,4894,1828,7255,456,7180,8746,3838,6404,6179,5617,3118,8078,9187,289,5989,1661,1204,8103,2,6234,7953,9013,5465,559,6769,9766,2565,7425,1409,3177,2304,6304,5005,9559,6760,2185,4657,598,8589,836,2567,1708,5266,1754,8349,1255,9767,5905,5711,9769,8492,3664,5134,3957,575,1903,3723,3140,5681,5133,6317,4337,7789,7675,3896,4549,6212,8553,1499,1154,5741,418,9214,1007,2172,7563,8614,8291,3469,677,4413,1961,4341,9547,5918,4916,7803,9641,4408,3484,1126,7078,7821,8915,1105,8069,9816,7317,2974,1315,8471,8715,1733,7685,6074,257,5249,4688,8549,5070,5366,2962,7031,6059,8861,9301,7328,6664,5294,8088,6500,6421,1518,4321,5336,2623,8742,1505,9941,1716,2820,4764,6783,906,2450,2857,7515,4051,7546,2416,9121,9264,1730,6152,1675,592,1805,9003,7256,7099,3444,3757,9872,4962,4430,1561,7586,3173,3066,3879,1241,2238,8643,8025,3144,7445,882,7012,1496,4780,9428,617,396,1159,3121,2072,1751,4926,7427,5359,8378,871,5468,8250,5834,9899,9811,9772,9424,2877,3651,7017,5116,8646,5042,4612,6092,2277,1624,7588,3409,1053,8206,3806,8564,7679,2230,6667,8958,6009,2026,7336,6881,3847,5586,9067,98,1750,8839,9522,4627,8842,2891,6095,7488,7934,708,3580,6563,8684,7521,9972,6089,2079,130,4653,9758,2360,1320,8716,8370,9699,6052,1603,3546,7991,670,3644,6093,9509,9518,7072,4703,2409,3168,2191,6695,228,2124,3258,5264,9645,9583,1354,1724,9713,2359,1482,8426,3680,6551,3148,9731,8955,4751,9629,6946,5421,9625,9391,1282,5495,6464,5985,4256,5984,4528,952,6212,6652,562,1476,6297,145,9182,8021,6211,1542,5856,4637,1574,2407,7785,1305,1362,2536,934,4661,4309,559,4052,1943,2406,516,4280,6662,2852,8808,7614,9064,1813,4529,6893,8110,4674,2427,2484,7237,3969,8340,1874,5543,7099,6011,3200,8461,8547,486,9474,9208,7397,9879,7503,9803,6747,1783,6466,9600,6944,432,8664,8757,4961,1909,6867,5988,4337,5703,3225,4658,4043,1452,6554,1142,7463,9754,5956,2363,241,1782,7923,7638,1661,5427,3794,8409,7210,260,8009,4154,692,3025,9263,2006,4935,2483,7994,5624,8186,7571,282,8582,9023,6836,6076,6487,6591,2032,8850,3184,3815,3125,7174,5476,8552,968,3885,2115,7580,8246,2621,4625,1272,1885,6631,6207,4368,4625,8183,2554,8548,8465,1136,7572,1654,7213,411,4597,5597,5613,7781,5764,8738,1307,7593,7291,8628,7830,9406,6208,6077,2027,833,7349,3912,7464,9908,4632,8441,8091,7187,6990,2908,4675,914,4562,8240,1325,9159,190,6938,3292,5954,2028,4600,9899,9319,3228,7730,5077,9436,159,7105,6622,7508,7369,4086,3768,2002,8880,8211,5541,2222,1119,216,3136,5682,4809,813,1193,4999,4103,4486,7305,6131,9086,7205,5451,2314,1287,528,8102,1446,3985,4724,5306,1355,5163,9074,9709,4043,7285,5250,2617,4756,1818,2105,6790,6627,2918,7984,7978,7021,2470,1636,3152,7908,8841,4955,222,6480,5484,4676,7926,5821,9401,3232,7176,916,8658,3237,1311,5943,8487,3928,7051,306,6033,3842,3285,8951,1826,7616,2324,648,9252,5476,8556,4445,6784])


# 复盘:找了个动态归纳法的python答案
# 思路是差不多的,但是代码量上被吊打...
# 另外一个解法是万能的双指针
# 哪天心情平复之后我再找时间做下试试吧

def maxProfit(prices):
    if len(prices) <= 1:
        return 0
    diff = [0 for _ in range(len(prices) - 1)]
    for i in range(len(prices) - 1):
        diff[i] = prices[i + 1] - prices[i]
    dp = [0 for _ in range(len(prices) - 1)]
    dp[0] = max(0, diff[0])
    max_profit = dp[0]
    for i in range(1, len(prices) - 1):
        dp[i] = max(0, diff[i] + dp[i - 1])
        max_profit = max(max_profit, dp[i])
    return max_profit

# ----------菜狗分割线----------
# 不行了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊!
# 这道题一开始我想的思路简直是我的智商盲区啊!草(中国语)
# 提交了 8遍都不过 总有些奇怪的通不过去的测试用例
# 然后顺着加条件吧 越加越多不说 明知道有重合的条件 然而还是过不去!
# 玛德我要重新写....
# 气的大晚上想怒喝monster啊啊啊啊!

# 自己都看不懂的黑历史!
# class Solution:
#     def maxProfit(self, prices):
#         if len(prices) == 0:
#             return 0
#         i = 0
#         keep_max_key = 0
#         keep_max_val = 0
#         result = 0
#         keep_diff = 0
#         for price in prices:
#             if i == 0:
#                 #  min
#                 keep_min_val = price
#                 keep_min_key = 0
#                 i += 1
#                 continue
#             if prices[i - 1] >= price and i + 1 < len(prices) and price < prices[i + 1]:
#                 # down
#                 if keep_min_val > price:
#                     keep_min_key, keep_min_val = i, price
#             elif prices[i - 1] < price and i + 1 < len(prices) and price >= prices[i + 1]:
#                 # up
#                 if keep_max_val < price:
#                     keep_max_key, keep_max_val = i, price
#                 keep_diff = result = result if keep_min_key > keep_max_key else keep_max_val - keep_min_val
#             elif not(keep_min_key == 0) and price > keep_max_val:
#                 keep_max_key, keep_max_val = i, price
#                 keep_diff = result = 0 if keep_min_key > keep_max_key else keep_max_val - keep_min_val
#             else:
#                 i += 1
#                 continue
#             i += 1
#
#         if keep_max_key == 0 or keep_max_key < keep_min_key < len(prices)+1 or (keep_max_val < prices[i-1]):
#             if len(prices) == 2:
#                 result = 0 if keep_min_val > price else price - keep_min_val
#             else:
#                 result = prices[i-1] - keep_min_val if prices[i-1] > keep_min_val else result
#         result = keep_diff if keep_diff > result else result
#         return result
